package offer;

@FunctionalInterface
public interface FindPeakElement {
    /**
     * A peak element is an element that is strictly greater than its neighbors.
     *
     * Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
     *
     * You may imagine that nums[-1] = nums[n] = -∞.
     *
     * You must write an algorithm that runs in O(log n) time.
     *
     * @param nums
     * @return
     */
    int findPeakElement(int[] nums);
}
class FindPeakElementImpl1 implements FindPeakElement{
    /**
     * o(n),o(1)
     * @param nums
     * @return
     */
    @Override
    public int findPeakElement(int[] nums) {
        // 平凡情况
        if(nums.length == 1){
            return 0;
        }else if(nums.length == 2){
            if(nums[0] > nums[1]){
                return 0;
            }else{
                return 1;
            }
        }
        int n = nums.length;
        if(nums[0] > nums[1]){
            return 0;
        }else if(nums[n - 1] > nums[n - 2]){
            return n - 1;
        }

        for (int i = 1; i < n - 1; i++) {
            int pre = nums[i - 1];
            int cur = nums[i];
            int next = nums[i + 1];
            if(pre < cur && cur > next){
                return i;
            }
        }
        return 0;
    }
}
class FindPeakElementImpl2 implements FindPeakElement{
    static final int[] TEST_01 = new int[]{1,2,3,2,1};
    public static void main(String[] args) {
        new FindPeakElementImpl2().findPeakElement(TEST_01);
    }
    /**
     * 由于存在两个虚拟元素nums[-1],nums[n] 他们的值为-∞。
     * 因此必定存在一个极值点位于下标0到n-1之间（可以类比罗尔定理，两个端点相等，至少存在一个极值点）
     * 二分查找
     * 设 a = nums[mid - 1], b = nums[mid] , c = nums[mid + 1]
     * 则存在下述三种情况
     * 1. b > a > c or b > c > a， 该情况 mid 就是一个可行解
     * 2. c > b > a ， 该情况 mid 右侧必有峰值
     * 3. a > b > c ， 该情况 mid 左侧必有峰值
     * 4. a > c > b or c > a > b， 该情况 mid 左侧右侧都存在峰值
     *
     * @param nums
     * @return
     */
    @Override
    public int findPeakElement(int[] nums) {
        // 平凡情况
        int n = nums.length;
        if(n == 1){
            return 0;
        }else if(nums[0] > nums[1]){
            return 0;
        }else if(nums[n - 1] > nums[n - 2]){
            return n - 1;
        }
        // 非平凡情况
        int left = 1, right = n - 2, mid = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            int a = nums[mid - 1];
            int b = nums[mid];
            int c = nums[mid + 1];
            if(b > a && b > c){
                break;
            }else if(c > b && b > a){
                left = mid + 1;
            }else if(a > b && b > c){
                right = mid - 1;
            }else{
                // 两侧都存在峰值，不妨取左侧
                right = mid - 1;
            }
        }
        return mid;
    }
}